package arithmetic.LeetCode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import utils.TreeNode;

/**
 * 230. 二叉搜索树中第K小的元素
 * 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
 *
 * 示例 1：
 * 输入：root = [3,1,4,null,2], k = 1
 * 输出：1
 *
 *
 * @author jiangfeng on 2023/10/15
 */
public class kthSmallest {
    public static void main(String[] args) {

        System.out.println(new Solution().kthSmallest(TreeNode.createTree(3,1,4,null,2),1));
    }
    static class  Solution {
        public  int kthSmallest(TreeNode root, int k) {
            //中序遍历非递归
            //List<TreeNode> list = new ArrayList(k);
            int num = 0;
            Stack<TreeNode> stack =  new Stack();
            TreeNode index = root;
            while(!stack.empty() || index != null){
                if(index!=null){
                    stack.push(index);
                    index = index.left;
                    continue;
                }
                TreeNode t = stack.pop();
                //list.add(t);
                num++;
                if(num==k){
                    return t.val;
                }
                index = t.right;
            }
            return -1;
        }

        public int kthSmallest1(TreeNode root, int k) {
            //中序遍历
            List<TreeNode> list = new ArrayList();
            centerIter(root,list);
            return list.get(k-1).val;
        }
        public void centerIter(TreeNode root,List<TreeNode> list) {
            //中序遍历
            if(root == null){
                return;
            }
            centerIter(root.left,list);
            list.add(root);
            centerIter(root.right,list);
        }
    }
}
